package model;

/**
 * This class allows us to find a LCS using a dynamic with a k-diagonal strip approach
 * 
 * @author Thomas Donzelle
 */
public class LCS_dynamic_approx {
	/**
	 * This function returns a common subsequence between a and b
	 * 
	 * @param a
	 *            the first sequence
	 * @param b
	 *            the second sequence
	 * @param approx
	 *            the stripe size
	 * @return a common subsequence
	 */
	public static String lcs(String a, String b, int approx) {
		int aLen = a.length();
		int bLen = b.length();
		int[][] tab = new int[aLen + 1][bLen + 1];
		double ratio = aLen / bLen; // to define diagonal of non-square matrix

		double jDiag;

		for (int i = 0; i < aLen; i++) {
			jDiag = i + ratio;
			for (int j = Math.max((int) jDiag - approx, 0); j < bLen && j <= i + approx; j++) {
				if (a.charAt(i) == b.charAt(j)) {
					tab[i + 1][j + 1] = tab[i][j] + 1;
				} else {
					tab[i + 1][j + 1] = Math.max(tab[i + 1][j],tab[i][j + 1]);
				}
			}
		}

		StringBuffer sb = new StringBuffer();
		for (int x = aLen, y = bLen; x > 0 && y > 0;) {
			if (tab[x][y] == tab[x - 1][y]) {
				x--;
			} else if (tab[x][y] == tab[x][y - 1]) {
				y--;
			} else {
				x--;
				y--;
				assert a.charAt(x) == b.charAt(y);
				sb.append(a.charAt(x));

			}
		}

		return sb.reverse().toString();
	}
}
